package base.Chapter00_Structures.C01_Array;

import org.testng.annotations.Test;

import java.util.HashMap;

/**
 * 功能说明：
 * 在nums数组中, 查找等于target的两个元素
 * 开发人员：@author MaLi
 */
public class L01_两数之和 {
    //方法1: 两层循环 时间复杂度O(n*n)
    public int[] twoSum1(int[] nums, int target) {
        if (nums == null || nums.length <= 1) {
            return null;
        }
        /*
            关键: 确定循环
            循环角标i: [0,length-2]
            循环角标j: [i+1, length-1]
         */
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (target == nums[i] + nums[j]) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    //方法2: 使用hash替代一层循环
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length <= 1) {
            return null;
        }
        //Step1: 放入hashmap结构: 当前元素的补数,当前元素的角标
        //Step2: 遍历hashmap, 查target-nums[i]
        //复杂度: O(n)
        HashMap<Integer, Integer> intMap = new HashMap<>(nums.length);

        intMap.put(target - nums[0], 0);
        for (int i = 1; i < nums.length; i++) {
            boolean b = intMap.containsKey(nums[i]);
            if (b) {
                return new int[]{intMap.get(nums[i]), i};
            }
            intMap.put(target - nums[i], i);
        }
        return null;
    }

    @Test
    public void testTwoSum2() {
        int[] nums = {2,7,11,15};
        int[] ints = twoSum(nums, 9);
        System.out.println(ints);
    }
}
